/*
 * @lc app=leetcode.cn id=1658 lang=javascript
 *
 * [1658] 将 x 减到 0 的最小操作数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var binary_search = function(arr, target){
  let head = 0, tail = arr.length - 1, mid;
  while(head <= tail){
    mid = (head + ((tail - head)>>1));
    if(arr[mid] === target) return mid;
    if(arr[mid] < target){
      head = mid + 1;
    } else {
      tail = mid - 1;
    }
  }
  return -1;
}
var minOperations = function(nums, x) {
  let leftSum = [0], rightSum = [0];
  for (let i = 0; i < nums.length; i++){
    leftSum[i+1] = leftSum[i] + nums[i];
  } 
  let length = nums.length;
  for (let i = length-1; i >= 0; i--){
    rightSum[length - i] = rightSum[length - i - 1] + nums[i]
  }

  // 筛选最大值
  let ans = -1;
  for (let i = 0; i < leftSum.length; i++) {
    let j = binary_search(rightSum, x - leftSum[i]);
    if(j === -1) continue;
    if(j + i > nums.length) continue;
    if(ans == -1 || ans > i+j) ans = i + j;
  }
  return ans;
};
// @lc code=end

